package com.llb666.java.leetcode;

/**
 *  ------------------ LeetCode1137
 * Created by 斌~
 * 2021/3/12 17:18
 */
public  class 泰波那契序列1137{
    /**
     * 泰波那契序列 Tn 定义如下： 
     *  0、1、1、2、4、7、13、24、44、81
     *  T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
     *  给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
     *   输入：n = 4
     *  输出：4
     *  解释：
     *  T_3 = 0 + 1 + 1 = 2
     *  T_4 = 1 + 1 + 2 = 4
     * @param n
     * @return
     */
    public static int tribonacci(int n) {
        int a = 0, b = 1, c = 1;
        while(n-- > 0) {
            c = a + b + c;
            b = c - a - b;
            a = c - a - b;
        }
        return a;
    }


    /**
     * 斐波那契数列
     * 0、1、1、2、3、5、8、13、21、34
     */
    public static  int fibonacci(int n){
        int  a =0 ,b =1;
        while (n-- > 0){
            //leetcode 	1125  需要取模操作
//            if (b >= 1000000007) {
//                b -= 1000000007;
//            }
           b = a + b;
           a = b - a;
        }
        return a;
    }

    /**
     *  Fibonacci.java
     * 输入：45
     * 输出：1134903170
     * 预期：134903163
     * @param args
     */
    public static void main(String[] args) {
        int n =44;
//        System.out.println(tribonacci(25));
        System.out.println(fibonacci(n));
        System.out.println(fib(n));
        System.out.println(fibonacci(n)-fib(n));
    }


    public static int fib(int n) {
        if (n <= 1) return n;
        int first = 0;
        int second = 1;
        int result = 0;
        while (--n > 0) {
            result = first + second;
            if (result >= 1000000007) {
                result -= 1000000007;
            }
            first = second;
            second = result;
        }
        return result;
    }
}
